package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月18日
*时间：下午2:01:06
*/
public class Q87 {
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    public TreeNode removeNode(TreeNode root, int value) {
        if (root == null) {
            return null;
        }
        TreeNode p = null;
        TreeNode c = root;
        while (c != null) {
            if (c.val > value) {
                p = c;
                c = c.left;
            } else if (c.val < value) {
                p = c;
                c = c.right;
            } else {
                if (p == null) {
                    if (c.left != null) {
                        root = c.left;
                    } else {
                        root = c.right;
                        break;
                    }
                } else {
                    if (p.val > c.val) {
                        if (c.left != null) {
                            p.left = c.left;
                        } else {
                            p.left = c.right;
                            break;
                        }

                    } else {
                        if (c.left != null) {
                            p.right = c.left;
                        } else {
                            p.right = c.right;
                            break;
                        }
                    }
                }
                insert(c.left, c.right);
                break;
            }
        }
        return root;
    }

    private void insert(TreeNode left, TreeNode right) {
        TreeNode c = left;
        while (true) {
            if (c.right == null) {
                c.right = right;
                break;
            }
            c = c.right;
        }
    }

    @Test
    public void testA() {
        TreeNode root = new TreeNode(5);
        TreeNode r1 = new TreeNode(3);
        TreeNode r2 = new TreeNode(8);
        TreeNode r3 = new TreeNode(1);
        TreeNode r4 = new TreeNode(2);
        TreeNode r5 = new TreeNode(9);
        TreeNode r6 = new TreeNode(7);
        root.left = r1;
        root.right = r2;
        r1.left = r3;
        r2.right = r5;
        r2.left = r6;
        r3.right = r4;
        TreeNode rs = removeNode(new TreeNode(8), 8);
        System.out.println(rs);
    }
}
